#pragma once
#include<iostream>
using namespace std;
template<class K,class V>
struct BSTreeNode
{
	BSTreeNode(const K& key,const V&value)
		:_key(key)
		,_value(value)
		, _left(nullptr)
		, _right(nullptr)
	{}
	K _key;
	V _value;
	BSTreeNode* _left;
	BSTreeNode* _right;
};
template<class K, class V>
class BSTree
{
	typedef BSTreeNode<K,V> Node;
public:
	bool Insert(const K& key, const V& value)
	{
		Node* newnode = new Node(key,value);
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else return false;
		}
		//
		if (key < parent->_key)
			parent->_left = newnode;
		else
			parent->_right = newnode;
			return true;
	}
	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)	
				cur = cur->_left;
		
			else if (cur->_key > key)
				cur = cur->_right;

			else return cur;
		}
		return nullptr;
	}
	bool Erase(const K& key)
	{
		Node* ret = Find(key);
		if (!ret)return false;
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_value < key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_value > key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				if (!cur->_left)
				{

				}
			}

		}
	}
	void _InOrder(Node* root) 
	{
		if (!root)return;
		cout << root->_value << ',';
		_InOrder(root->_left);
		_InOrder(root->_right);
	}
	void InOrder()
	{
		_InOrder(_root);
	}
private:
	Node* _root = nullptr;
};


